package twobranchTree.preorderTraversal;

import java.util.LinkedList;
import java.util.List;

/**
 * @Date 2020/2/9
 * @author 王光浩
 * @Description 给出一个二叉树，使用前序遍历这个二叉树。
 * @Thinking 使用迭代方法——仅仅使用栈实现。
 *           复杂度分析：时间复杂度O（n），空间复杂度O（2n）——n为节点数
 */
public class MethodThree {
	public List<Integer> preorderTraversal(TreeNode root) {
		LinkedList<TreeNode> stack=new LinkedList<TreeNode>(); //栈，实现先进后出
		List<Integer> result=new LinkedList<Integer>();
		TreeNode tem=null;
		if(root!=null)stack.add(root);
		while(!stack.isEmpty()) {
			tem=stack.removeLast();
			result.add(tem.val);
			if(tem.right!=null)stack.add(tem.right);
			if(tem.left!=null)stack.add(tem.left);
		}
		return result;
	}
}
